#include <vector>
#include <functional>
#include <iostream>
#include <algorithm>
using namespace std;

namespace apex
{
	// 仿函数类
	template <class T>
	class less
	{
	public:
		bool operator()(const T &left, const T &right) const
		{
			return left < right;
		}
	};
	template <class T>
	class greater
	{
	public:
		bool operator()(const T &left, const T &right) const
		{
			return left > right;
		}
	};

	// template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type> >
	template <class T, class Container = vector<T>, class Compare = less<T>>
	class priority_queue
	{
	private:
		Container _con;
		Compare _Com;

	public:
		// 构造函数
		priority_queue()
			: _con()
		{
		}
		// 迭代器构造
		template <class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
			: _con(first, last)
		{
			// while (first != last)
			// {
			// 	_con.push_back(*first);
			// 	++first;
			// }

			// 下调建堆法
			for (int i = static_cast<int>(_con.size() - 1 - 1) / 2; i >= 0; --i)
			{
				adjust_down(i);
			}
		}

		// 入队
		void push(const T &x)
		{
			// 尾插数据
			_con.push_back(x);
			// 向上调整
			adjust_up(static_cast<int>(_con.size()) - 1);
		}

		// 出队
		void pop()
		{
			if (empty())
				return;

			// 堆顶与堆尾交换
			// std::swap(_con[0], _con[_con.size() - 1]);
			std::swap(_con.front(), _con.back());

			// 删除现堆尾(原堆顶)
			_con.pop_back();

			adjust_down(0);
		}

		// 取队头
		const T &top() const
		{
			// return _con.front();
			return _con[0];
		}

		// 判空
		bool empty() const
		{
			return _con.empty();
		}

		// 队大小
		size_t size() const
		{
			return _con.size();
		}

	private:
		// 上调logN
		void adjust_up(size_t child)
		{
			size_t parent = (child - 1) / 2;
			while (child > 0)
			{

				// if (_con[parent] > _con[child])   //小堆
				// if (_con[parent] < _con[child])   //大堆

				if (_Com(_con[parent], _con[child])) // 大堆
				{
					std::swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}
		// 下调logN
		void adjust_down(size_t parent)
		{
			size_t child = parent * 2 + 1;
			while (child < static_cast<int>(_con.size()))
			{
				// if (child + 1 < _con.size() && _con[child] > _con[child + 1])    //找real小孩子
				// if (child + 1 < _con.size() && _con[child] < _con[child + 1])    //找real大孩子

				if (child + 1 < _con.size() && _Com(_con[child], _con[child + 1])) // 找real大孩子
				{
					++child;
				}

				// if (_con[parent] > _con[child])   //小堆
				// if (_con[parent] < _con[child])   //大堆

				if (_Com(_con[parent], _con[child])) // 大堆
				{
					std::swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}
	};
}
// 测试主函数
int main()
{
	apex::priority_queue<int> p;
	p.push(1);
	p.push(3);
	p.push(2);
	p.push(5);
	p.push(4);

	while (!p.empty())
	{
		cout << p.top() << " ";
		p.pop();
	}
	cout << endl;
	return 0;
}